package com.majie.algorithm.sort;


import com.majie.common.SwapUtils;

/**
 * 选择排序
 * <p>
 * 拿出第一个,与其他比较,最小的放最左边,依次类推
 * <p>
 * 时间复杂度
 * 第一次内循环比较N - 1次，然后是N-2次，N-3次，……，最后一次内循环比较1次。
 * 共比较的次数是 (N - 1) + (N - 2) + ... + 1，求等差数列和，得 (N - 1 + 1)* N / 2 = N^2 / 2。
 * 舍去最高项系数，其时间复杂度为 O(n^2)。
 * <p>
 * 虽然时间复杂度和冒泡排序一样
 * 但是性能略优于冒泡排序
 *
 * @author majie
 * @date 2018/5/8.
 */
public class SelectionSort {

    private static void sort(int[] arr, int left, int right) {

        if (left >= right) {
            return;
        }

        //假设左边第一个为最小值,然后找到最小值跟它交换
        for (int i = left; i <= right; i++) {
            //找到最小值的索引
            int minIndex = i;
            for (int j = i + 1; j <= right; j++) {

                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }

            SwapUtils.swap(arr, i, minIndex);
        }

    }


    /**
     * 测试
     *
     * @param args
     */
    public static void main(String[] args) {
        int[] arr = {10, 6, 8, 3, 6, 5, 9, 4, 3, 1};
        sort(arr, 0, arr.length - 1);
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}
